package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// 因为有负数， 所以需要采用维护前缀和的方式去寻找目标值
// prefix[j] - prefix[i] = target.  等价于 prefix[j] - target = prefix[i]
func pathSum(root *TreeNode, targetSum int) int {
	cnt := 0
	prefixMap := make(map[int]int, 0)
	// 添加0进去，计算根元素前缀和
	prefixMap[0] = 1
	var dfs func(root *TreeNode, curSum int)

	// 中序遍历
	dfs = func(node *TreeNode, curSum int) {
		if node == nil {
			return
		}
		// 根
		curSum += node.Val
		cnt += prefixMap[curSum-targetSum]
		prefixMap[curSum] += 1
		// 左
		dfs(node.Left, curSum)
		// 右
		dfs(node.Right, curSum)
		prefixMap[curSum] -= 1
		if prefixMap[curSum] == 0 {
			delete(prefixMap, curSum)
		}
	}
	dfs(root, 0)
	return cnt
}
